package com.demo.datastructure.reorder.quickSort;

import com.demo.datastructure.reorder.Example;

/**
 * @author ljr
 * @version 1.0
 * @description: 快排练习
 * @date 2021/10/1 12:39
 */
public class SimlpeQuickSort2 implements Example {


    @Override
    public void sort(Comparable[] a, int low, int high) {
        if(low >= high) return;
        int mid = partition(a, low , high);
        sort(a, low, mid-1);
        sort(a, mid+1, high);
    }

    private int partition(Comparable[] a, int low, int high) {
        int min = low;
        Comparable value = a[high];
        for(int i = low; i < high; i++){
            if(less(a[i],value)){
                Comparable lowValue = a[i];
                a[i] = a[min];
                a[min++] = lowValue;
            }
        }

        a[high] = a[min];
        a[min] = value;
        return min;
    }
}
